package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/22 13:15
 * @description：https://leetcode-cn.com/problems/repeated-string-match/
 */
public class 重复叠加字符串匹配 {
    @Test
    public void test() {
        Solution solution = new Solution();
    }

    class Solution {
        public int repeatedStringMatch(String a, String b) {
            return 1;
        }

        public int kmpSearch(String str1, String str2){
            int[] next = kmpNext(str2);
            System.out.println(Arrays.toString(next));
            for (int i = 0, j = 0; i < str1.length(); i++) {
                while(j > 0 && str1.charAt(i) != str2.charAt(j)){
                    j = next[j - 1];
                }
                if(str1.charAt(i) == str2.charAt(j)){
                    j++;
                }
                if(j == str2.length()){
                    return i - j + 1;
                }
            }
            return -1;
        }

        public int[] kmpNext(String dest){
            int[] next = new int[dest.length()];
            next[0] = 0;
            for (int i = 1, j = 0; i < dest.length(); i++) {
                while(j > 0 && dest.charAt(i) != dest.charAt(j)){
                    j = next[j - 1];
                }
                if (dest.charAt(i) == dest.charAt(j)) {
                    j++;
                }
                next[i] = j;
            }
            return next;
        }
    }
}
